#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <stdbool.h>
using namespace std;


//int main() {
//    int num = 0;
//    cin >> num;
//    vector<int> p;
//    while (num--)
//    {
//        int a = 0;
//        cin >> a;
//        p.push_back(a);
//    }
//    num = p.size();
//    int ret = 0;
//    int min = 100;
//    for (int i = 1; i < num; i++)
//    {
//        if (p[i] > p[i - 1])
//        {
//            if (p[i - 1] < min)
//            {
//                min = p[i - 1];
//            }
//            if ((p[i] - min) > ret)
//            {
//                ret = p[i] - min;
//            }
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}






//int getLongestPalindrome(string s) {
//    // write code here
//    int a = s.size();
//    vector<vector<int>> dp(a + 1, vector<int>(a + 1));
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            if (i == 5 && j == 0)
//            {
//                int num = 0;
//            }
//            if (i == j)
//            {
//                dp[i][j] = 1;
//            }
//            
//            else {
//                if (s[i] == s[j])
//                {
//                    if (i - j < 2)
//                    {
//                        dp[i][j] =1;
//                    }
//                    else if(dp[i-1][j+1]==1)
//                    {
//                        dp[i][j] = 1;
//                    }
//                    else
//                    {
//                        dp[i][j] = 0;
//                    }
//                }
//                else {
//                    dp[i][j] = 0;
//                }
//            }
//        }
//    }
//    int max = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            if (dp[i][j] == 1 && i - j > max)
//            {
//                max = i - j;
//            }
//        }
//    }
//    cout << max+1;
//    return 0;
//}
//
//int main()
//{
//    string s = "cabbac";
//    getLongestPalindrome(s);
//
//    return 0;
//}



//int row[8] = { -2,-2,-1,1,2,2,1,-1 };
//int col[8] = { -1,1,2,2,1,-1,-2,-2 };
//
//int main() {
//    int m, n;
//    cin >> m >> n;
//    int x, y;
//    cin >> x >> y;
//    x++, y++;
//    vector<vector<int>> dp(m+2,vector<int>(n+2,0));
//    dp[0][1] = 1;
//    for (int i = 1; i <= m+1; i++)
//    {
//        for (int j = 1; j <= n+1; j++)
//        {
//            if (i == 2 && j == 3)
//            {
//                int num = 0;
//            }
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            for (int k = 0; k < 8; k++)
//            {
//                if (i == x + row[k] && j == y + col[k])
//                {
//                    dp[i][j] = 0;
//                }                
//            }
//            if (i == x && j == y)
//            {
//                dp[i][j] = 0;
//            }
//            cout << dp[i][j];
//        }
//        cout << endl;
//    }
//    cout << dp[m+1][n+1];
//    return 0;
//}